package com.zwj.interview.动态规划;

/**
 * 题目：在一个m×n（m、n均大于0）的格子中，每个位置都有一个数字。
 * 一个机器人每步只能向下或向右，请计算它从格子的左上角到达右下角的路径的数字之和的最小值
 */
public class 机器人走格子 {

    /**
     * 分析：
     * 用函数f（i，j）表示从格子的左上角坐标为（0，0）的位置（用grid[0][0]表示）
     * 出发到达坐标为（i，j）的位置（用grid[i][j]表示）的路径的数字之和的最小值。
     * 如果格子的大小为m×n，那么f（m-1，n-1）就是问题的解
     * <p>
     * <p>
     * 当行号i、列号j都大于0时，机器人有两种方法可以到达坐标为（i，j）的位置。它既可以从坐标为（i-1，j）的位置向下走一步，
     * 也可以从坐标为（i，j-1）的位置向右走一步，因此，f（i，j）等于f（i-1，j）与f（i，j-1）的最小值加上grid[i][j]
     */

    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0];
        for (int j = 1; j < grid[0].length; j++) {
            dp[0][j] = grid[0][j] + dp[0][j - 1];
        }

        /**
         * 二维数组dp保存状态转移方程的计算结果，f（i，j）保存在“dp[i][j]”中。如果表格grid有m行n列，
         * 那么二维数组dp也有m行n列，二维数组dp中的每个元素都被计算一次
         */
        for (int i = 1; i < grid.length; i++) {
            dp[i][0] = grid[i][0] + dp[i - 1][0];
            for (int j = 1; j < grid[0].length; j++) {
                int prev = Math.min(dp[i - 1][j], dp[i][j - 1]);
                dp[i][j] = grid[i][j] + prev;
            }
        }
        return dp[grid.length - 1][grid[0].length - 1];
    }


}
